package com.wx.leetcode;

/**
 * @desc:  最长回文子串
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 *
 * 输入: "cbbd"
 * 输出: "bb"
 *
 * @author: wx
 * @time: 2020/4/8 1:32 PM
 */
public class LongestPalindromeTopic {

    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        int strLen = s.length();
        //记录长度
        int length = 1;
        //左边下标
        int left;
        //右边下标
        int right;

        //开始下标
        int startIndex = 0;
        //结束下标
        int endIndex = 0;

        for (int i = 1; i < strLen; i++) {

            left = i - 1;
            right = i + 1;
            int tempLength = 1;

            //比较右边
            while (right < strLen && s.charAt(i) == s.charAt(right)){
                tempLength++;
                right++;
            }

            //比较左边
            while (left >= 0 && s.charAt(i) == s.charAt(left)){
                tempLength++;
                left --;
            }


            //比较左边与右边
            while (left >= 0 && right < strLen && s.charAt(left) == s.charAt(right)){
                tempLength = tempLength + 2;
                left --;
                right ++;
            }

            if (tempLength > length) {
                length = tempLength;
                startIndex = left;
                endIndex = right;
            }
        }

        if (length  == 1){
            endIndex++;
        } else {
            startIndex++;
        }

        return s.substring(startIndex,endIndex);

    }
    
    public static void main(String args[]) {
        System.out.println(longestPalindrome("cbbd"));
    } 
    

}
